import java.util.Arrays;

public class Leetcode1691 {
    public static void main(String[] args) {
        System.out.println(maxHeight(new int[][]{{36, 46, 41}, {15, 100, 100}, {75, 91, 59}, {13, 82, 64}}));
//        System.out.println(maxHeight(new int[][]{{50, 45, 20}, {95, 37, 53}, {45, 23, 12}}));
//        System.out.println(maxHeight(new int[][]{{38, 25, 45}, {76, 35, 3}}));
//        System.out.println(maxHeight(new int[][]{{7, 11, 17}, {7, 17, 11}, {11, 7, 17}, {11, 17, 7}, {17, 7, 11}, {17, 11, 7}}));

    }

    public static int maxHeight(int[][] cuboids) {
        if (cuboids.length == 1) {
            return Math.max(cuboids[0][0], Math.max(cuboids[0][1], cuboids[0][2]));
        }

        for (int[] cuboid : cuboids) {
            Arrays.sort(cuboid);
        }

        //很慢 不知道为什么
//        Arrays.sort(
//                cuboids,
//                Comparator.<int[]>comparingInt(arr -> arr[0])
//                          .thenComparingInt(arr -> arr[1])
//                          .thenComparingInt(arr -> arr[2])
//        );

        //快100ms
        Arrays.sort(cuboids, (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] != b[1] ? a[1] - b[1] : a[2] - b[2]);

        int[] currentRes = new int[cuboids.length];
        currentRes[0] = cuboids[0][2];
        int finalRes = currentRes[0];
        for (int i = 1; i < cuboids.length; i++) {
            for (int j = 0; j < i; j++) {
                if (cuboids[j][1] <= cuboids[i][1] && cuboids[j][2] <= cuboids[i][2] && currentRes[j] > currentRes[i]) {
                    currentRes[i] = currentRes[j];
                }
            }

            currentRes[i] += cuboids[i][2];
            if (currentRes[i] > finalRes) {
                finalRes = currentRes[i];
            }
        }

        return finalRes;
    }
}
